package mess;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_51_tryAgain {
    public static void main(String[] args) {
        List<List<String>> lists = solveNQueens(9);
        for (List<String> list : lists) {
            for (String s : list) {
                System.out.println(s);
            }
            System.out.println();
        }
    }

    private static List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();

        if (n == 1) {
            List<String> list = new ArrayList<>();
            list.add("Q");
            res.add(list);
            return res;
        }
        if (n == 2 || n == 3)
            return res;

        for (int first = 0; first < n; first++) {
            char[][] chars = new char[n][n];

            //第一行初始化
            chars[0][first] = 'Q';

            //排除同一列
            int temp = 1;
            while (temp < n) {
                chars[temp][first] = '.';
                temp++;
            }
            //排除/斜边
            temp = 1;
            while (temp < n && first - temp >= 0) {
                chars[temp][first - temp] = '.';
                temp++;
            }
            //排除\斜边
            temp = 1;
            while (temp < n && first + temp < n) {
                chars[temp][first + temp] = '.';
                temp++;
            }
            //递归搜索
            backTrick(res, chars, 1, 0, n);
        }
        return res;
    }

    private static void backTrick(List<List<String>> res, char[][] chars, int i0, int j0, int n) {
        //i0, j0位置往下搜寻
        for (int i = i0; i < n; i++) {
            int start = 0;
            if (i == i0)
                start = j0;
            for (int j = start; j < n; j++) {
                //第 i > 1 行
                if (chars[i][j] == '.' && j == n - 1) {
                    //递归出口
                   return;
                }
                if (chars[i][j] == '.')
                    continue;

                //1.复制chars
                char[][] newChars = new char[n][n];
                for (int k = 0; k < n; k++) {
                    for (int l = 0; l < n; l++) {
                        newChars[k][l] = chars[k][l];
                    }
                }
                if (j < n - 1){
                    backTrick(res, newChars, i, j + 1, n);
                }

                chars[i][j] = 'Q';
                //排除同一列
                int temp = 1;
                while (i + temp < n) {
                    chars[i + temp][j] = '.';
                    temp++;
                }
                //排除/斜边
                temp = 1;
                while (i + temp < n && j - temp >= 0) {
                    chars[i + temp][j - temp] = '.';
                    temp++;
                }
                //排除\斜边
                temp = 1;
                while (i + temp < n && j + temp < n) {
                    chars[i + temp][j + temp] = '.';
                    temp++;
                }

                if (i == n - 1) {
                    //搜寻到符合条件的目标, 构造结果
                    for (int k = 0; k < n; k++) {
                        for (int m = 0; m < n; m++) {
                            if (chars[k][m] != 'Q')
                                chars[k][m] = '.';
                        }
                    }
                    List<String> newRes = new ArrayList<>();
                    for (int r = 0; r < n; r++) {
                        StringBuilder sb = new StringBuilder();
                        for (char c : chars[r]) {
                            sb.append(c);
                        }
                        newRes.add(sb.toString());
                    }
                    res.add(newRes);
                }
                break;
            }
        }
    }
}
